package dp;

public class 使用最小花费爬楼梯_746 {

    public int minCostClimbingStairs(int[] cost) {
        //return cursion(cost.length , 0, cost);
        // 建议
        for(int i = 2; i< cost.length ; i++) {
            cost[i] = Math.min(cost[i - 2], cost[i - 1]) + cost[i];
        }
        // 使用数组  避免数组越界
        return Math.min(cost[cost.length -1], cost[cost.length -2]);
    }
    // n 是当前节点
    public int cursion(int n, int curCost, int[] cost) {
        if(n<2) {
            return curCost ;
        }
        // 不建议反着算  会把所有可能路径都递归完  很耗时
        curCost = Math.min(cursion(n - 2, curCost + cost[n-2], cost), cursion(n - 1, curCost + cost[n-1], cost));
        return curCost;
    }
}
